package P452_最小数量的箭引爆气球;

import java.util.Arrays;

//数量最少的箭引爆气球

//区间类的，两步走，1.排序，2从头到尾遍历，用贪心算法依次更新
public class Solution {
    public int findMinArrowShots(int[][] points) {
        //注意边界条件！！！
        if(points.length == 0){
            return 0;
        }
        Arrays.sort(points, (a,b)-> {
            if(a[1] > b[1]){
                return 1;
            }else if(a[1] < b[1]){
                return -1;
            }else{
                return 0;
            }
        });
        int count = 1;
        //按照右边排序后遍历，第一次是第一个区间作为公用区间，然后跟后面的判断重复区间，这个可用的公共区间逐步缩小，
        //当某个point不再这个已经缩小的区间里面后，需要重新再右边开个区间，然后这个区间再次逐步缩小
        int[] area = points[0];
        for(int i = 1;i < points.length;i++){
            if(points[i][0] > area[1]){
                count++;
                area = points[i];
            }else{
                area[0] = Math.min(points[i][0] , area[0]);
            }
        }
        return count;

    }
    public static void main(String args[]){
        int[][] points = new int[][]{{1,2},{3,4},{5,6},{7,8}};
        System.out.println(new Solution().findMinArrowShots(points));
    }
}
